package ru.susu.algebra.ranks;

import java.io.BufferedReader;
import java.io.FileReader;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Comparator;
import java.util.Date;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import junit.framework.Assert;

import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

import com.google.common.collect.Lists;
import com.google.common.collect.Maps;

import ru.susu.algebra.number.MapPrimeNumbersProvider;
import ru.susu.algebra.pair.Pair;
import ru.susu.algebra.util.LRUHashMap;
import ru.susu.algebra.util.NumberUtilities;
import ru.susu.algebra.util.SortedArrayMap;

/**
 * @author akargapolov
 * @since: 04.04.2011
 */
public class FullDPRanksCounterNewSquare
{
	private static Logger _log = Logger.getLogger("ranks");

	private static boolean DEBUG = false;

	public static int START_NUMBER = 1;
	public static int END_NUMBER = 1000;
	private static int KDP_CACHE_SIZE = 1 << 20;

	/**
	 * Максимальное простое должно быть не больше, чем NUMBER / 4, иначе не получится элемента MAX_PRIME + 3 * MAX_PRIME
	 */
	public static int MAX_PRIME_NUMBER = END_NUMBER / 4 + 1;

	public static int DEPTH_SAVE = 1;

	private static Map<Integer, BitSet> _factors = new NumbersBitSetFactorizationProvider().performOperation(END_NUMBER);

	private static Map<Integer, Integer> _primes = new MapPrimeNumbersProvider().performOperation(END_NUMBER);

	private static Integer[] _index2Primes = new Integer[END_NUMBER];

	private static long[][][] _dp = new long[END_NUMBER + 1][END_NUMBER + 1][4];

	static
	{
		for (int i = 0; i <= END_NUMBER; i++)
			for (int j = 0; j <= END_NUMBER; j++)
				Arrays.fill(_dp[i][j], -1);

		Map<Integer, BitSet> tmp = Maps.newHashMap();
		int length = new MapPrimeNumbersProvider().performOperation(MAX_PRIME_NUMBER).size();
		for (Entry<Integer, BitSet> entry : _factors.entrySet())
		{
			BitSet bitset = new BitSet(length);
			for (int i = 0; i < bitset.size(); i++)
			{
				bitset.set(i, entry.getValue().get(i));
			}
			tmp.put(entry.getKey(), bitset);
		}
		_factors = tmp;

		for (Entry<Integer, Integer> entry : _primes.entrySet())
		{
			_index2Primes[entry.getValue()] = entry.getKey();
		}
	}

	private static Map<BitSet, BigInteger>[][][] _data = (Map<BitSet, BigInteger>[][][])Array.newInstance(Map.class, END_NUMBER + 3, END_NUMBER + 3, 4);

	private static Map<BitSet, Object[]> _cache = Maps.newHashMap();//new LRUHashMap<BitSet, BitSet>(MAX_NODES / 10);
	private static Map<BigInteger, BigInteger> _intcache = Maps.newHashMap();//new LRUHashMap<BigInteger, BigInteger>(MAX_NODES / 10);

	private static long _nodes = 0, _nullsCached = 0, _maxBits = 0;

	public static void main(String[] args) throws Exception
	{
		BasicConfigurator.configure();
		initializeTrueRanks();

		for (int i = START_NUMBER; i <= END_NUMBER; i++)
		{
			Date start = new Date();
			BigInteger squares = recCounter(i, 1, 0, new BitSet(_primes.size()), 0, NumberUtilities.squareRoot(BigInteger.valueOf(i)).intValue());

			if (i % 10 == 0)
				System.gc();

			long rank = recDP(i, 1, 0) - squares.longValue();
			_log.info("rank[" + i + "] - " + rank);
			_log.info("squares[" + i + "] - " + squares.longValue());
			_log.info("nodes - " + _nodes);
			_log.info("total - " + Runtime.getRuntime().totalMemory() / 1000000);
			_log.info("free - " + Runtime.getRuntime().freeMemory()/ 1000000);
			_log.info("used - " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory())/ 1000000);
			_log.info("time - " + (new Date().getTime() - start.getTime()) + "ms");
			_log.info("BitsetCache size - " + _cache.size() + " IntCache size - " + _intcache.size() + " Nulls cached - " + _nullsCached);

			if (RANKS.containsKey(i))
				Assert.assertEquals("Ранги должны совпадать", RANKS.get(i).longValue(), rank);
		}
		_log.info("max bits - " + _maxBits);
		_log.info("finished");
		Thread.sleep(120000);
	}

	protected static BigInteger recCounter(int i, int k, int shift, BitSet bitset, int depth, int sqrtN) throws Exception
	{
		if (i == 0 && shift == 0)
		{
			if (bitset.isEmpty())
				return BigInteger.ONE;
		}
		else if (k > i)
		{
			return BigInteger.ZERO;
		}

		if (_data[i][k][shift] == null)
			//_data[i][k][shift] = Maps.newTreeMap(new BitSetComparator());
			//_data[i][k][shift] = new HashMap<BitSet, BigInteger>(1, 0.9f);
			_data[i][k][shift] = new SortedArrayMap<BitSet, BigInteger>(new BitSetComparator());
		BigInteger result = _data[i][k][shift].get(bitset);
		if (result != null)
		{
			return result;
		}


		/**
		 * Глубина не должна превышать sqrt(n) - очевидно выполняется по построению (как формула суммы)
		 */
		if (depth > sqrtN)
			return BigInteger.ZERO;

		/**
		 * Сумма простых не должна превышать n - иначе никак не получим квадрат (самая минимальная сумма - сумма без произведений)
		 */
		/*if (getPrimesSum(bitset) > i) входит в следующий случай
			return BigInteger.ZERO;*/

		/**
		 * Динамикой 2^n рассматриваем все разбиения простых на группы с наложением условия, что каждая группа >=k
		 */
		if (getMinPrimeSumK(bitset, k, INF) > i)
		{
			return BigInteger.ZERO;
		}

		_maxBits = Math.max(_maxBits, bitset.cardinality());

		result = BigInteger.ZERO;
		for (int j = k; j <= i; j += 2)
		{
			if (recDP(i - j, j + 2, (shift + 1 - j + 4 * i) % 4) > 0 && isGood(i, j))
			{
				BitSet tmp = (BitSet) bitset.clone();
				tmp.xor(_factors.get(j));
				result = result.add(recCounter(i - j, j + 2, (shift + 1 - j + 4 * i) % 4, tmp, depth + 1, sqrtN));
			}
		}

		if (depth % DEPTH_SAVE == 1 || DEPTH_SAVE <= 1)
		{
			if (result.equals(BigInteger.ZERO))
				_nullsCached++;
			_data[i][k][shift].put(getBitSet(bitset), getBigInteger(result));
			_nodes++;

			if (_nodes % 100000 == 0)
			{
				_log.info(_nodes + " nodes");
			}
		}

		if (DEBUG)
		{
			_log.info(i + " " + k + " " + shift + " " + bitset + " = " + result);
		}

		return result;
	}

	private static int getPrimesSum(BitSet bitset)
	{
		int result = 0;
		for (int i = 0; i < bitset.length(); i++)
			if (bitset.get(i))
				result += _index2Primes[i];
		return result;
	}

	private static int KDP_LENGTH = 20;
	private static int KDP_SIZE = 1 << KDP_LENGTH;
	private static int[] _kdp = new int[KDP_SIZE];
	private static int INF = 1 << 15;

	private static Map<String, Integer> _kdata = new LRUHashMap<String, Integer>(KDP_CACHE_SIZE);

	private static int getMinPrimeSumK(BitSet bitset, int k, int inf)
	{

		String key = bitset.toString() + "_" + k;

		Integer result = _kdata.get(key);
		if (result != null)
			return result;

		List<Integer> primes = Lists.newArrayList();
		for (int i = 0; i < bitset.length(); i++)
			if (bitset.get(i))
				primes.add(_index2Primes[i]);

		if (primes.size() > KDP_LENGTH)
			throw new RuntimeException("");

		Arrays.fill(_kdp, 0, 1 << primes.size(), -1);

		/*return recKDP(primes, (1 << primes.size()) - 1, k, inf);*/
		result = recKDP(primes, (1 << primes.size()) - 1, k, inf);
		_kdata.put(key, result);
		return result;
	}

	private static int recKDP(List<Integer> primes, int mask, int k, int inf)
	{
		if (_kdp[mask] != -1)
			return _kdp[mask];

		if (mask == 0)
			return 0;

		int result = inf;
		int lastBit = 0;
		for (int i = 0;i < primes.size();i++)
			if ((mask & (1 << i)) > 0)
				lastBit = 1 << i;


		for (int i = mask; (i & lastBit) > 0; i = (i - 1) & mask)
		{
			int tmp = 1;
			for (int j = 0;j < primes.size() && tmp < result;j++)
				if ((i & (1 << j)) > 0)
				{
					tmp *= primes.get(j);
				}
			if (tmp < k)
			{
				if (k % tmp == 0)
					tmp = k;
				else
				{
					int tmp1 = (k / tmp + 1) * tmp;
					if (tmp1 % 2 == 0)
						tmp1 += tmp;
					tmp = tmp1;
				}
			}

			if (tmp < result)
			{
				result = Math.min(tmp + recKDP(primes, mask ^ i, k, inf), result);
			}
		}
		_kdp[mask] = result;
		return result;
	}

	private static Boolean[][] _isGood = new Boolean[END_NUMBER + 1] [END_NUMBER + 1];

	private static boolean isGood(int n, int k)
	{
		if (k == 9)
			return true;
		Boolean result = _isGood[n][k];
		if (result != null)
			return result;
		Pair<Integer, Integer>[] factorization = NumberUtilities.factorization(BigInteger.valueOf(k));
		result = true;
		if (factorization.length > 0)
		{
			Integer maxPrime = factorization[factorization.length - 1].getKey();
			if (maxPrime > MAX_PRIME_NUMBER || maxPrime * 3 > n)
				result = false;
		}
		_isGood[n][k] = result;
		return result;
	}

	private static String DELIMITER = "_";

	private static String[][][] KEYS = new String[END_NUMBER + 5][END_NUMBER + 5][4];

	protected static String getKey(int i, int k, int shift)
	{
		if (KEYS[i][k][shift] == null)
		{
			KEYS[i][k][shift] = new StringBuilder().append(i).append(DELIMITER).append(k).append(DELIMITER).append(shift).toString();
		}
		return KEYS[i][k][shift];
	}

	public static long recDP(int n, int k, int shift)
	{
		if (n == 0)
		{
			if (shift == 0)
				return 1;
			else
				return 0;
		}
		if (k > n)
			return 0;
		if (_dp[n][k][shift] != -1)
			return _dp[n][k][shift];

		_dp[n][k][shift] = recDP(n - k, k + 2, (shift + 1 - k + 4 * 1000) % 4) + recDP(n, k + 2, shift);
		return _dp[n][k][shift];
	}

	protected static BitSet getBitSet(BitSet bitset)
	{
		Object[] result = _cache.get(bitset);
		if (result == null)
		{
			result = new Object[2];
			_cache.put(bitset, result);
			result[0] = bitset;
			result[1] = 0;
		}
		result[1] = (Integer) result[1] + 1;
		return (BitSet) result[0];
	}

	protected static void decreaseBitSetAndWeak(BitSet bitset)
	{
		Object[] result = _cache.get(bitset);
		if (result != null)
		{
			result[1] = (Integer) result[1] - 1;
			Integer value = (Integer) result[1];
			if (value == 0)
			{
				_cache.remove(bitset);
			}
		}
	}

	protected static BigInteger getBigInteger(BigInteger value)
	{
		BigInteger result = _intcache.get(value);
		if (result == null)
		{
			_intcache.put(value, value);
			result = value;
		}
		return result;
	}

	public static class BitSetComparator implements Comparator<BitSet>
	{
		@Override
		public int compare(BitSet bitset1, BitSet bitset2)
		{
			if (bitset1.length() != bitset2.length())
				return bitset1.length() - bitset2.length();

			if (bitset1.equals(bitset2))
				return 0;

			for (int i = 0;i < bitset1.length();i++)
				if (bitset1.get(i) != bitset2.get(i))
					return bitset1.get(i) ? 1 : -1;

			return 0;
		}
	}

	private static final int NUM_LINES = 16;
	private static final int OUR_LINE = 9;

	private static Map<Integer, Long> RANKS = Maps.newHashMap();

	private static void initializeTrueRanks() throws Exception
	{
		BufferedReader reader = new BufferedReader(new FileReader("Ranks/ranks800.txt"));

		//read legend
		for (int i = 0;i<= NUM_LINES;i++)
			reader.readLine();

		int number = 1;
		int counter = 0;
		while(1 == 1)
		{
			String line = reader.readLine();
			if (line == null)
				break;

			if (counter % NUM_LINES == OUR_LINE)
			{
				String s = line.substring(3).trim();
				RANKS.put(number++, Long.parseLong(s));
			}

			counter++;
		}

	}
}
